public class Solution1081 {
    public String smallestSubsequence(String s) {
        boolean[] exist = new boolean[26];
        int[] count = new int[26];
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(!exist[c - 'a']){
                while(sb.length() > 0 && sb.charAt(sb.length() - 1) > c && count[sb.charAt(sb.length() - 1) - 'a'] > 0){
                    exist[sb.charAt(sb.length() - 1) - 'a'] = false;
                    sb.deleteCharAt(sb.length() - 1);
                }
                sb.append(c);
                exist[c - 'a'] = true;
            }
            count[c - 'a']--;
        }
        return sb.toString();
    }
}
